Матч 241, Путешествие по воздуху (AirTravel)

Дивизион 2, Уровень 3

На планете, имеющей форму шара с радиусом 4000, задано множество аэропортов. Координаты i - го аэропорта задаются парой (широта, долгота) = (latitude[i], longitude[i]), заданных в градусах. В ячейке canTravel[i] содержатся номера аэропортов, в которые можно вылетать из i - го. Если существует путь из i - го аэропорта в j - ый, то необязательно существует путь из j - го в i - ый.

Из аэропорта с номером origin необходимо доставить груз в аэропорт с номером destination, пролетев наименьшее расстояние. Нумерация аэропортов начинается с 0.

Расстояние от точки (lat₁, lon₁) до (lat₂, lon₂) на шаре радиуса radius равно

radius * acos(sin(lat₁) * sin(lat₂) +

cos(lat₁) * cos(lat₂) * cos(lon₁ - lon₂))

Класс: AirTravel

Метод: double shortestTrip(vector<int> latitude,

vector<int> longitude,

vector<string> canTravel, int origin, int destination)

Ограничения: latitude, longitude и longitude содержат от 1 до 20 элементов, -89 £ latitude[i] £ 89, -179 £ longitude[i] £ 179, canTravel[i] является строкой, содержащей числа от 0 до n – 1, где n – количество элементов в latitude, 0 £ origin, destination £ n – 1, никакие два аэропорта не имеют одинаковых координат.

Вход. Массивы latitude и longitude содержат координаты (широту и долготу) аэропортов.

Выход. Наименьшее расстояние, которое следует преодолеть для перелета из аэропорта origin в destination.

Пример входа

latitude	longitude	canTravel	origin	destination
{0, 0, 70}	{90, 0, 45}	{"2", "0 2", "0 1"}	0	1
{0, 0, 70}	{90, 0, 45}	{"1 2", "0 2", "0 1"}	0	1
{0, 20, 55}	{-20, 85, 42}	{"1", "0", "0"}	0	2

Пример выхода

10612.237799994255

6283.185307179586

-1.0

РЕШЕНИЕ

алгоритм Дейкстры + геометрия

Заполним матрицу расстояний m, положив m[i][j] равным расстоянию между i - ым и j - ым аэропортом, если путь между ними существует, и +¥ иначе. Расстояние между аэропортами вычисляем по формуле, приведенной в условии. Поскольку широта и долгота заданы в градусах, при вычислении тригонометрических функций следует переводить их в радианы.

При помощи алгоритма Дейкстры ищем кратчайший путь от аэропорта origin до destination. Если по окончании работы алгоритма Дейкстры d[destination] содержит +¥, то возвращаем -1 (требуемого пути не существует).

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <sstream>

#include <cmath>

#define MAX 21

#define INF 2100000000

#define K acos(-1.0) / 180.0

using namespace std;

double m[MAX][MAX], d[MAX];

int used[MAX], n;

void Init(int origin)

{

int i, j;

for(i = 0; i < n; i++)

{

for(j = 0; j < n; j++)

m[i][j] = INF / 2;

d[i] = INF / 2;

}

memset(used,0,sizeof(used));

d[origin] = 0;

}

void Relax(int i, int j)

{

if (d[j] > d[i] + m[i][j]) d[j] = d[i] + m[i][j];

}

int Find_Min(void)

{

int i, v;

double min = INF / 2;

for(i = 0; i < n; i++)

if (!used[i] && d[i] < min) min = d[i], v = i;

return v;

}

double Dist(double lat1, double lon1, double lat2, double lon2)

{

return 4000.0 * acos(sin(K * lat1) * sin(K * lat2) + cos(K * lat1) *

cos(K * lat2) * cos(K*lon1 - K*lon2));

}

class AirTravel

{

public:

double shortestTrip(vector<int> latitude, vector<int> longitude,

vector<string> canTravel, int origin, int destination)

{

int i, j, v;

n = latitude.size(); Init(origin);

for(i = 0; i < canTravel.size(); i++)

{

stringstream in(canTravel[i]);

while(in >> j)

m[i][j] = Dist(latitude[i],longitude[i],latitude[j],longitude[j]);

}

for(i = 0; i < n; i++)

{

v = Find_Min();

for(j = 0; j < n; j++)

if (!used[j]) Relax(v,j);

used[v] = 1;

}

return (d[destination] > INF / 3) ? -1 : d[destination];

}

};